#define _CRT_SECURE_NO_WARNINGS 1

class Solution {
public:
    int mySqrt(int x) {
        long long left = 0, right = INT_MAX;
        while (left <= right)
        {
            long long mid = (right - left) / 2 + left;
            if (mid * mid > x)
                right = mid - 1;
            else if (mid * mid < x)
                left = mid + 1;
            else
                return mid;
        }
        return right;
    }
};